package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/06/02
 */
public class 第400场单周赛 {

    public static void main(String[] args) {

        // [[6,11],[7,13],[8,9],[5,8],[3,13],[11,13],[1,3],[5,10],[8,13],[3,9]]
        System.out.println(countDays2(14, new int[][]{{6, 11}, {7, 13}, {8, 9}, {5, 8}, {3, 13}, {11, 13}, {1, 3}, {5, 10}, {8, 13}, {3, 9}}));
    }

    public int minimumChairs(String s) {
        int max = 0;
        int cur = 0;
        for (char c : s.toCharArray()) {
            if (c == 'E') {
                cur++;
                max = Math.max(max, cur);
            } else {
                cur--;
            }
        }
        return max;
    }

    /**
     * 差分数组
     */
    public int countDays(int days, int[][] meetings) {
        int cnt = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        for (int[] meeting : meetings) {
            diffMap.put(meeting[0], diffMap.getOrDefault(meeting[0], 0) - 1);
            diffMap.put(meeting[1] + 1, diffMap.getOrDefault(meeting[1] + 1, 0) + 1);
        }

        int num = 0;
        for (int i = 1; i <= days; i++) {
            num += diffMap.getOrDefault(i, 0);
            if (num == 0) {
                cnt++;
            }
        }
        return cnt;
    }

    /**
     * 逆向思维
     * 统计工作日的天数，总天数-工作日
     */
    public static int countDays2(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        int subSum = 0;

        subSum += meetings[0][1] - meetings[0][0] + 1;
        int maxRight = meetings[0][1];

        for (int i = 1; i < meetings.length; i++) {
            int[] curMeet = meetings[i];
            int[] preMeet = meetings[i - 1];

            if (curMeet[1] <= maxRight) {
                continue;
            }
            if (curMeet[0] > preMeet[1]) {
                subSum += curMeet[1] - Math.max(curMeet[0], maxRight + 1) + 1;

            } else if (curMeet[0] == preMeet[1]) {
                subSum += curMeet[1] - Math.max(curMeet[0], maxRight) + 1 - 1;

            } else {

                subSum += curMeet[1] - maxRight;

            }

            maxRight = Math.max(maxRight, curMeet[1]);
        }

        return days - subSum;
    }

    /**
     * 模拟+顺序遍历
     */
    public String clearStars(String s) {
        List<Integer>[] cnt = new List[26];
        for (int i = 0; i < cnt.length; i++) {
            cnt[i] = new ArrayList();
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ('*' == c) {
                findAndRemove(cnt);
            } else {
                cnt[c - 'a'].add(i);
            }
        }
        Map<Integer, Character> map = new HashMap<>();
        for (int i = 0; i < cnt.length; i++) {
            for (Integer idx : cnt[i]) {
                map.put(idx, (char) ('a' + i));
            }
        }
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            Character c = map.get(i);
            if (c != null) {
                stringBuilder.append(c);
            }
        }

        return stringBuilder.toString();
    }

    private void findAndRemove(List[] cnt) {
        for (List list : cnt) {
            if (list.size() > 0) {
                list.remove(list.size() - 1);
                return;
            }
        }
    }
}
